package com.mc.algorithm;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

public class Sudoku {
    private static ArrayList<Point> list;//记录需要填的位置
    private static int[][] mat;//记录矩阵
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            
           	mat = new int[9][9];
            list = new ArrayList<Point>();
            for(int i = 0;i<9;i++)
                for(int j=0;j<9;j++){
               		mat[i][j]=sc.nextInt();
            		if(mat[i][j]==0)
                        list.add(new Point(i,j));
            	}
            setNum(0);
            for(int i = 0;i<9;i++){
            	for(int j=0;j<8;j++){
                	System.out.print(mat[i][j]+" ");
                }
            	System.out.println(mat[i][8]);
            }
        }
    }
    
    public static boolean setNum(int loc){
        if(loc==list.size())
        	 return true;
        Point curr = list.get(loc);
        int i = curr.i;
        int j = curr.j;
        int org = mat[i][j];//原始值
        HashSet<Integer> set = getSet(i,j);//得到可选集合
        
        if(set==null)
            return false;
        Iterator<Integer> iter = set.iterator();
        while(iter.hasNext()){//逐个填入
            int num = iter.next();
            mat[i][j]= num;
            boolean res = setNum(loc+1);
        	if(res)
                return true;
        }
        mat[i][j] = org;
        return false;
    }
    public static HashSet<Integer> getSet(int i,int j){
        HashSet<Integer> rowSet = new HashSet<Integer>();
        HashSet<Integer> colSet = new HashSet<Integer>();
        
        HashSet<Integer> tarSet = new HashSet<Integer>();
        HashSet<Integer> tarSet2 = new HashSet<Integer>();
        for(int k=0;k<9;k++){
        	tarSet.add(k+1);
        	tarSet2.add(k+1);
        }
      
        for(int m=0;m<9;m++){
			if(mat[i][m]!=0)
                rowSet.add(mat[i][m]);
            if(mat[m][j]!=0)
                colSet.add(mat[m][j]);
        }
        tarSet.removeAll(rowSet);
        tarSet2.removeAll(colSet);
        tarSet.retainAll(tarSet2);
        return tarSet;
    }
    static class Point{
        int i;
        int j;
        Point(int a,int b){
            i = a;
            j = b;
        }
    }
	
}
